﻿//
// KwCombinatorics v1.4.x
// Copyright © 2009-2012 - Kasey Osborn (Kasewick@gmail.com)
// Ms-PL - Use and redistribute freely
//
// File: Product.cs
//

using System;
using System.Collections.Generic;
using System.Text;

namespace Kw.Combinatorics
{
    /// <summary>
    /// Represents a join of values from an array of supplied ranges.
    /// </summary>
    /// <remarks>
    /// <para>
    /// Use the <see cref="Width"/> property to get the number of joined elements.
    /// Use the <see cref="Rank"/> property to choose a row from an ordered
    /// cartesian product table.
    /// Use the <see cref="GetEnumerator">default enumerator</see> to enumerate over all
    /// elements of a row.
    /// Use <see cref="Rows"/> to enumerate over an ordered table of all possible
    /// joins.
    /// Use the <see cref="Permute">Permute</see>
    /// method to rearrange a supplied list based on the current row values.
    /// Use the <see cref="P:Kw.Combinatorics.Product.Item(System.Int32)">indexer</see>
    /// to get an element of the row.
    /// </para>
    /// <para>
    /// For more information, see:<br />
    /// <br />
    /// <em>http://en.wikipedia.org/wiki/Cartesian_product</em>
    /// </para>
    /// </remarks>
    /// <example>
    /// <para>
    /// Iterating over <c>Product (2, 3)</c> produces:
    /// </para>
    /// <para>
    /// { 0, 0 }<br />
    /// { 0, 1 }<br />
    /// { 0, 2 }<br />
    /// { 1, 0 }<br />
    /// { 1, 1 }<br />
    /// { 1, 2 }
    /// </para>
    /// </example>
    public class Product :
        ICloneable,
        IComparable,
        System.Collections.IEnumerable,
        IComparable<Product>,
        IEquatable<Product>,
        IEnumerable<int>
    {
        private long rank;          // Current row index.
        internal int[] sizes;       // Range of each column.
        internal long[] factors;    // Running multiple of sizes.

        #region Constructors

        /// <summary>
        /// Make an empty <see cref="Product"/>.
        /// </summary>
        public Product ()
        {
            this.sizes = new int[0];
            this.factors = new long[0];

            Height = 0;
            this.rank = 0;
        }


        /// <summary>
        /// Make a copy of a <see cref="Product"/>.
        /// </summary>
        /// <param name="source">Instance to copy.</param>
        public Product (Product source)
        {
            this.sizes = new int[source.sizes.Length];
            this.factors = new long[source.factors.Length];

            source.sizes.CopyTo (this.sizes, 0);
            source.factors.CopyTo (this.factors, 0);
            Height = source.Height;
            this.rank = source.rank;
        }


        /// <summary>
        /// Make a <see cref="Product"/> from the supplied column ranges.
        /// </summary>
        /// <param name="sizes">Range of each column.</param>
        /// <example>
        /// <code source="Examples\ProductExample01\ProductExample01.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentOutOfRangeException">
        /// When any column range less than 0.
        /// </exception>
        public Product (int[] sizes)
        {
            this.sizes = new int[sizes.Length];
            sizes.CopyTo (this.sizes, 0);

            this.factors = new long[this.sizes.Length];
            Height = sizes.Length == 0 ? 0 : 1;

            for (int x = this.sizes.Length - 1; x >= 0; --x)
            {
                if (this.sizes[x] < 0)
                    throw new ArgumentOutOfRangeException ("sizes", "Value is less than zero.");

                this.factors[x] = Height;
                Height *= this.sizes[x];
            }
        }

        #endregion

        #region Properties

        /// <summary>
        /// Total count of all distinct sequences for the product's column ranges.
        /// </summary>
        public long Height
        { get; private set; }


        /// <summary>
        /// Row index of the ordered cartesian product table.
        /// </summary>
        /// <remarks>
        /// Any assigned value out of range will be normalized to (0..<em>Height</em>-1).
        /// </remarks>
        /// <example>
        /// <code source="Examples\ProductExample03\ProductExample03.cs" lang="cs" />
        /// </example>
        public long Rank
        {
            get
            {
                return rank;
            }
            set
            {
                if (Height == 0)
                    rank = 0;
                else
                {
                    // Normalize the new rank.
                    rank = value % Height;
                    if (rank < 0)
                        rank += Height;
                }
            }
        }


        /// <summary>
        /// Enumerate over the rows of an ordered table of all joins.
        /// </summary>
        /// <remarks>
        /// If the start row is not at rank 0, the enumeration will wrap around
        /// so that <see cref="Height"/> items are always produced.
        /// </remarks>
        /// <example>
        /// <code source="Examples\ProductExample01\ProductExample01.cs" lang="cs" />
        /// </example>
        public IEnumerable<Product> Rows
        {
            get
            {
                if (Height > 0)
                {

                    long startRank = rank;
                    for (Product current = new Product (this); ; )
                    {
                        yield return current;
                        current.Rank = current.Rank + 1;
                        if (current.rank == startRank)
                            break;
                    }
                }
            }
        }


        /// <summary>
        /// Get the range of a column.
        /// </summary>
        /// <param name="column">Column index.</param>
        /// <returns>Size of the range at <em>column</em>.</returns>
        public long Size (int column)
        { return sizes[column]; }


        /// <summary>
        /// Number of columns in the cartesian product table.
        /// </summary>
        public int Width
        { get { return sizes.Length; } }


        /// <summary>
        /// Get an element of the cartesian product at the supplied column.
        /// </summary>
        /// <param name="index">Index value.</param>
        /// <returns>Sequence value at <em>index</em>.</returns>
        /// <example>
        /// <code source="Examples\ProductExample03\ProductExample03.cs" lang="cs" />
        /// </example>
        /// <exception cref="IndexOutOfRangeException">
        /// When <em>index</em> not in range (0..<em>Width</em>-1).
        /// </exception>
        public int this[int index]
        {
            get
            {
                long r = rank;
                if (index > 0)
                    r %= factors[index - 1];

                return (int) (r / factors[index]);
            }
        }

        #endregion

        #region Methods

        /// <summary>Make a copy of this <see cref="Product"/>.</summary>
        /// <remarks>Implements the deprecated IClone interface.</remarks>
        /// <returns>Copy of the object.</returns>
        public object Clone ()
        { return new Product (this); }


        /// <summary>Compare two cartesian product ranks.</summary>
        /// <param name="obj">Target of the comparison.</param>
        /// <returns>Comparison difference sign of the cartesian product ranks.</returns>
        public int CompareTo (object obj)
        { return CompareTo (obj as Product); }


        /// <summary>Compare two cartesian product ranks.</summary>
        /// <returns>Comparison difference sign of the ranks.</returns>
        /// <param name="other">A cartesian product row.</param>
        public int CompareTo (Product other)
        {
            if ((object) other == null)
                return 1;

            int result = this.Width - other.Width;

            if (result == 0)
                if (this.Rank > other.Rank)
                    result = 1;
                else if (this.Rank < other.Rank)
                    result = -1;

            return result;
        }


        /// <summary>Indicate whether two cartesian product rows have the same rank.</summary>
        /// <param name="obj">A cartesian product row to compare against.</param>
        /// <returns><b>true</b> if the parameter is the same as this row;
        /// otherwise, <b>false</b>.</returns>
        public override bool Equals (object obj)
        { return Equals (obj as Product); }


        /// <summary>Indicate whether two cartesian product rows have the same rank.</summary>
        /// <param name="other">A cartesian product row to compare against.</param>
        /// <returns><b>true</b> if the parameter is the same as this
        /// <see>row</see>; otherwise, <b>false</b>.</returns>
        public bool Equals (Product other)
        { return (object) other != null && other.Rank == Rank && other.Width == Width; }


        /// <summary>Get an object-based enumerator of the elements.</summary>
        /// <returns>object-based elemental enumerator.</returns>
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator ()
        { return GetEnumerator (); }


        /// <summary>Enumerate over all elements of a cartesian product.</summary>
        /// <returns>An <c>IEnumerator&lt;int&gt;</c> for this row.</returns>
        /// <example>
        /// <code source="Examples\ProductExample05\ProductExample05.cs" lang="cs" />
        /// </example>
        public IEnumerator<int> GetEnumerator ()
        {
            for (int index = 0; index < Width; index++)
                yield return this[index];
        }


        /// <summary>Returns the hash oode for this row.</summary>
        /// <returns>A 32-bit signed integer hash code.</returns>
        public override int GetHashCode ()
        { return unchecked ((int) rank); }


        /// <summary>
        /// Apply a row to select from the supplied lists or arrays.
        /// </summary>
        /// <typeparam name="T">Type of items to rearrange.</typeparam>
        /// <param name="arrangement">New arrangement for items.</param>
        /// <param name="source">List of List of Items or arrays to rarrange.</param>
        /// <returns>List of rearranged items.</returns>
        /// <example>
        /// <code source="Examples\ProductExample04\ProductExample04.cs" lang="cs" />
        /// </example>
        /// <exception cref="ArgumentException">When not enough source sets.</exception>
        /// <exception cref="IndexOutOfRangeException">
        /// When supplied source list is too small.
        /// </exception>
        public static List<T> Permute<T> (Product arrangement, IList<IList<T>> source)
        {
            if (source.Count < arrangement.Width)
                throw new ArgumentException ("Not enough supplied values.", "source");

            List<T> result = new List<T> (arrangement.Width);

            for (int i = 0; i < arrangement.Width; ++i)
                result.Add (source[i][arrangement[i]]);

            return result;
        }


        /// <summary>
        /// Provide readable form of the sequence at the current rank.
        /// </summary>
        /// <remarks>Result is enclosed in braces and separated by commas.</remarks>
        /// <returns>A <c>string</c> that represents the sequence.</returns>
        /// <example>
        /// <code source="Examples\ProductExample03\ProductExample03.cs" lang="cs" />
        /// </example>
        public override string ToString ()
        {
            if (Height == 0)
                return ("{ }");

            StringBuilder result = new StringBuilder ("{ ");

            for (int i = 0; ; )
            {
                result.Append (this[i]);

                ++i;
                if (i >= Width)
                    break;

                result.Append (", ");
            }

            result.Append (" }");

            return result.ToString ();
        }

        #endregion

        #region Static methods

        /// <summary>Indicate whether two cartesian product rows are equal.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if supplied rows are equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator == (Product param1, Product param2)
        {
            if ((object) param1 == null)
                return (object) param2 == null;
            else
                return param1.Equals (param2);
        }


        /// <summary>Indicate whether two cartesian product rows are not equal.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if supplied rows are not equal;
        /// otherwise, <b>false</b>.</returns>
        public static bool operator != (Product param1, Product param2)
        { return !(param1 == param2); }


        /// <summary>Indicate whether the left cartesian product row is less than
        /// the right cartesian product row.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if the left cartesian product row is less than
        /// the right cartesian product row otherwise, <b>false</b>.</returns>
        public static bool operator < (Product param1, Product param2)
        {
            if ((object) param1 == null)
                return (object) param2 != null;
            else
                return param1.CompareTo (param2) < 0;
        }


        /// <summary>Indicate whether the left cartesian product row is greater than or
        /// equal to the right cartesian product row.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if the left cartesian product row is greater than or
        /// equal to the right cartesian product row otherwise, <b>false</b>.</returns>
        public static bool operator >= (Product param1, Product param2)
        { return !(param1 < param2); }


        /// <summary>Indicate whether the left cartesian product row is greater than
        /// the right cartesian product row.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if the left cartesian product row is greater than
        /// the right cartesian product row otherwise, <b>false</b>.</returns>
        public static bool operator > (Product param1, Product param2)
        {
            if ((object) param1 == null)
                return false;
            else
                return param1.CompareTo (param2) > 0;
        }


        /// <summary>Indicate whether the left cartesian product row is less than or equal to
        /// the right cartesian product row.</summary>
        /// <param name="param1">A cartesian product row.</param>
        /// <param name="param2">A cartesian product row.</param>
        /// <returns><b>true</b> if the left cartesian product row is less than or equal to
        /// the right cartesian product row otherwise, <b>false</b>.</returns>
        public static bool operator <= (Product param1, Product param2)
        { return !(param1 > param2); }


        /// <summary>
        /// Increment the rank of the supplied product by 1.
        /// The increment operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A product row to modify.</param>
        /// <returns>The given product with the next higher rank.</returns>
        public static Product operator ++ (Product param)
        {
            param.Rank = param.rank + 1;
            return param;
        }


        /// <summary>
        /// Decrement the rank of the supplied product by 1.
        /// The decrement operator can appear before or after its operand.
        /// </summary>
        /// <param name="param">A product row to modify.</param>
        /// <returns>The given product with the previous lower rank.</returns>
        public static Product operator -- (Product param)
        {
            param.Rank = param.Rank - 1;
            return param;
        }

        #endregion
    }
}
